/*
 * winnerTree.h
 * This file is part of Jamming
 *
 * Copyright (C) 2012 - Yi
 *
 * Jamming is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * Jamming is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with Jamming. If not, see <http://www.gnu.org/licenses/>.
 */


#ifndef __WINNERTREE_H__
#define __WINNERTREE_H__
#include "deque.h"
#include "queue.h"
namespace Heap {
    template <class T,class Tcontainer = std::deque<int>, class ExternalChannel=std::priority_queue<T>, class _TypeCompare=std::less<T> >
    class WinnerTree {
        Tcontainer internalNodes;
        ExternalChannel<T>* externalNodes;
        int nExternalNodes,maxDepth,lowExt,offset;
        inline int getMaxDepth() {
            if(nExternalNodes<=0) return -1;
            int d=0;
            while( (1<<d)+1 < nExternalNodes) d++;
            return d;
        }
        inline int getLowExt() {return (nExternalNodes-1<<maxDepth)<<1;}
        inline int getOffset() {return (1<<(maxDepth+1))-1;}
        inline int parent(int idx) {
            return idx<lowExt? ((idx+1+offset)>>1)-1: ((nExternalNodes+idx-lowExt)>>1)-1; 
        };
        inline int __Ewinner__(int idx1,int idx2) { 
            if(!externalNodes[idx1] || !externalNodes[idx2]) return -1; //not able to play.
            if(!externalNodes[idx1].empty() ||!externalNodes[idx2].empty()) return -1;
            return (externalNodes[idx1].top() > externalNodes[idx2].top())? idx1:idx2;  // maximum heap, compare function?
        } //winner of contest of external nodes
        inline int __Iwinner__(int idx1,int idx2) { 
            if(internalNodes[idx1]<0 || internalNodes[idx2]<0) return -1; 
            if(!externalNodes[internalNodes[idx1]] || !externalNodes[internalNodes[idx2]]) return -1;
            if(!externalNodes[internalNodes[idx1]].empty() ||!externalNodes[internalNodes[idx2]].empty()) return -1;
            return (externalNodes[internalNodes[idx1]].top() >externalNodes[internalNodes[idx2]].top())? idx1:idx2;
        } // winner of contest of internal nodes.
        inline upwardContest(int idx){
            while( idx !=0) {
                if(idx&1) {
                    internalNodes[idx>>1]=__Iwinner__(idx-1,idx);
                } 
                idx=idx>>1;
            }
        };
        replay(int idx){
            if(idx==lowExt && n&1) { //play with internal winner
                internalNodes[(n>>1)-1]=__winner__(internalNodes[n-2],lowExt);
                upwardContest(parent(idx));
                return;
            }
            if(idx&1) {
                //even nodes(idx=nth-1) idx=1,3,5,...
                internalNodes[parent(idx)]=__Ewinner__(idx,idx-1); upwardContest(parent(idx));
            } else {
                //odd nodes idx=0,2,4,...
                internalNodes[parent(idx)]=__Ewinner__(idx,idx+1); upwardContest(parent(idx));
            }
        };
        organize() {
            maxDepth=getMaxDepth();
            lowExt=getLowExt();
            offset=getOffset();
            for(register int i=0;i<lowExt;i+=2) {internalNodes[parent(i)]=__Ewinner__(i,i+1); upwardContest(parent(i));}
            if(n&1) { // n is odd
                internalNodes[(n>>1)-1]=__winner__(internalNodes[n-2],lowExt);
                upwardContest(parent(i));
                i++;
            }
            for(;i<n;i+=2) {internalNodes[parent(i)]=__Ewinner__(i,i+1);upwardContest(parent(i));}
        };
        public:
        WinnerTree(int nChannel=1) {
            nExternalNodes=nChannel;
        };
        modifyChannel(int idx,ExternalChannel channel) {
            externalNodes[idx]=channel;
            replay(idx);
        };
        addExternalChannel(ExternalChannel* channel) {
            externalNodes.push_back(channel);
            nExternalNodes++;
            organize();
        };
        removeExternalChannel(int idx) {
            externNodes.remove(idx);
            nExternalNodes--;
            organize();
        };
        T top() {
            if(internalNodes[0]<0 || !internalNodes[0]) raise 1;//NotInitialized();
            return externalNodes[internalNodes[0]];
        };
        ExternalChannel<T>* topChannel() {
            return internalNodes[0];
        };
        T pop() {
            if(internalNodes[0]<0 || !internalNodes[0]) raise 1;//NotInitialized();
            if(!internalNodes[0].empty()) return internalNodes[0].pop();
            else removeExternalChannel(internalNodes[0]);
        };
    };
    class Buffer : public BinaryHeap {
    
    };
};

#endif /* __WINNERTREE_H__ */

